#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 1e9;
int n;
int t[maxn], lz[maxn*2], a[maxn];
void pushup(int o){
    t[o] = t[o*2] + t[o*2+1]; 
    // + ^ max min gcd 皆可
}

void build(int l=1, int r=n, int o=1){
    if ( l==r ){
        t[o] = a[l];
        return;
    }
    int mid = (l+r) >> 1;
    build(l,mid,o*2); build(mid+1,r,o*2+1);
    pushup(o);
}

void pushdown(int l, int r, int o){
    if ( lz[o]==0 ) return;

    int mid = (l+r) / 2, ls = o*2, rs = o*2+1;

    t[ls] += lz[o] * (mid-l+1);
    t[rs] += lz[o] * (r-mid);

    lz[ls] += lz[o];
    lz[rs] += lz[o];

    lz[o] = 0;
}

void add(int l, int r, int x, int s=1, int e=n, int o=1){
    if ( l<=s && e<=r ){
        t[o] += (e-s+1) * x;
        lz[o] += x;
        return;
    }

    pushdown(s,e,o);

    int mid = (s+e) / 2;

    if ( mid >= l ) add(l,r,x,s,mid,o*2);
    if ( mid+1 <= r ) add(l,r,x,mid+1,e,o*2+1);

    pushup(o);
}

int query(int l, int r,int s=1, int e=n, int o=1){
    if ( l<=s && e<=r ){
        return t[o];
    }

    int res = 0;
    
    pushdown(s,e,o);
    int mid = (s+e) / 2;
    if ( l<=mid ) res += query(l,r,s,mid,o*2);
    if ( mid+1 <= r ) res += query(l,r,mid+1,e,o*2+1);

    return res;
}